//
// Created by ASUS on 2024/7/10/星期三.
//
#include <bits/stdc++.h>
using namespace std;


class SuffixArray {
	vector<int> sa,rk,height,tmp;
	string s;
public:
	SuffixArray(string& s) {
		int n = s.size();
		this->s=s;
		sa.resize(n+1);
		rk.resize(n+1);
		tmp.resize(n+1);
		height.resize(n+1);
		for (int i = 0; i <= n; i++) {
			sa[i] = i;
			rk[i] = s[i];
		}
		int k;
		auto comp_sa = [&](int i, int j)->bool {
			if(rk[i]!=rk[j]){
				return rk[i]<rk[j];
			}else{
				int ri=i+k<n?rk[i+k]:-1;
				int rj=j+k<n?rk[j+k]:-1;
				return ri<rj;
			}
		};
		for (k = 1; k < n; k <<= 1) {
			sort(sa.begin(), sa.end(), comp_sa);
			tmp[sa[0]]=0;
			for(int i=0;i<n;i++){
				tmp[sa[i+1]]=tmp[sa[i]]+(comp_sa(sa[i],sa[i+1])?1:0);
			}
			for(int i=0;i<n;i++){
				rk[i]=tmp[i];
			}
		}
		for(int i=0;i<n;i++){
			rk[sa[i]]=i;
		}
	}

	vector<int> get_sa(){
		return sa;
	}
	vector<int> get_rk(){
		return rk;
	}
	vector<int> get_height(){
		int i,j,k=0,n=height.size()-1;
		for(i=0;i<n;i++){
			k=0;
			j=sa[rk[i]-1];
			while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) k++;
			height[rk[i]]=k;
		}
		return height;
	}
};
